/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

 //先考虑最简单的情况——根、左孩子、有孩子
 //假设左孩子的最大路径和为left，右孩子的最大路径和为right，根的值为val
 //那么，包含根节点的最大路径和就是 root->val + (left > 0 ? left : 0) + (right > 0 ? right : 0)
 //如果这棵树还有父节点，那么就要向父节点返回这棵子树的最大路径和，即root->val + max((left > 0 ? left : 0), (right > 0 ? right : 0)
 //      注意不能是左右相加，否则会分叉
 //最后，利用后序遍历 先求左右子树的最大路径和，再利用左右子树的最大路径和求根的最大路径和，就可以解决问题
class Solution {
    int ret_max = INT_MIN;
    int _maxPathSum(TreeNode* root) {
        if (root == nullptr)
            return 0;
        
        int left = _maxPathSum(root->left);
        int right = _maxPathSum(root->right);
        ret_max = max(ret_max, root->val + (left > 0 ? left : 0) + (right > 0 ? right : 0));

        return root->val + max((left > 0 ? left : 0), (right > 0 ? right : 0));
    }
public:
    int maxPathSum(TreeNode* root) {
        _maxPathSum(root);

        return ret_max;
    }
};